public class maxSubArray {
    /**
     * 最大子数组和
     * 给你一个整数数组nums，找到一个额具有最大和的连续子数组，返回最大和
     * 子数组就是数组中的一个 连续 部分
     */
    public static int method(int[] nums){
        // 利用动态规划，对当前的数组和前一个包含数字的子数组之和
        int ans = Integer.MIN_VALUE;
        int[] dp = new int[nums.length + 1]; //dp代表的是以nums[i]结尾的最大子数组和
        dp[0] = nums[0];
        ans = dp[0];
        for(int i=1; i< nums.length;i++){
            dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
            ans = Math.max(ans,dp[i]);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums={-2, 1, 3, -4, 2, -4, -1, -5, 7, 9};
        System.out.println(method(nums));
    }
}
